package tree;

import offer.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
//                root 1
//       left 2       right 3
//    left 4  right 5  left 6   right 7
public class leetCode662_widthOfBinaryTree {
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int max = 0;
        while (!queue.isEmpty()){
            int with = queue.size();
            max = Math.max(max,queue.getLast().val - queue.getFirst().val + 1);
            while (with > 0){
                TreeNode poll = queue.remove();
                if(poll.left != null){
                    poll.left.val = 2 * poll.val;
                    queue.add(poll.left);
                }
                if(poll.right != null){
                    poll.right.val = 2 * poll.val + 1;
                    queue.add(poll.right);
                }
                with--;
            }
        }
        return max;
    }

    public int widthOfBinaryTree2(TreeNode root) {
        if(root == null) return 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int max = 0;
        while (!queue.isEmpty()){
            int with = queue.size();
            max = Math.max(max,queue.getLast().val - queue.getFirst().val + 1);
            while (with > 0){
                TreeNode poll = queue.remove();
                if(poll.left != null){
                    poll.left.val = 2 * poll.val;
                    queue.add(poll.left);
                }
                if(poll.right != null){
                    poll.right.val = 2 * poll.val + 1;
                    queue.add(poll.right);
                }
                with--;
            }
        }
        return max;

    }

}
